START

# pocet veci, kapacita batohu
VAR n, k: INT;
# sirka a vyska tabulky
VAR sirka, vyska: INT;
# matice vah, cen, tabulka 
VAR vahy, ceny, tab: ARRAY;
# pomocne promenne
VAR i, v, s, vaha, cena, a, b: INT;
VAR fileIn, fileOut, konf, konfig:STRING;

fileIn = 'input.txt';
fileOut = 'output.txt';
open(0, fileIn);

n = read(fileIn); k = read(fileIn); vahy = [n]; ceny = [n];
vaha = 0;
cena = 1;

# nacteni vstupu
for (i=0; i<n; i=i+1) {
    vahy[i]=read(fileIn);   
    ceny[i]=read(fileIn);	
}

close(fileIn);

# vahy, ceny
# ceny[0]=38; ceny[1]=86; ceny[2]=112; ceny[3]=1; ceny[4]=66;
# ceny[5]=97; ceny[6]=195; ceny[7]=85; ceny[8]=42; ceny[9]=223;

# vahy[0]=27; vahy[1]=2; vahy[2]=41; vahy[3]=1; vahy[4]=25;
# vahy[5]=1; vahy[6]=34; vahy[7]=3; vahy[8]=50; vahy[9]=12;

sirka = n + 1;
vyska = k + 1;

# inicializace tabulky
tab = [sirka][vyska][2+n];

# vynulovani prvniho radku a sloupce
for (i=0; i<sirka; i=i+1) {
    tab[i][0][vaha] = 0;
    tab[i][0][cena] = 0;
    for (v=2; v<n+2; v=v+1) {
        tab[i][0][v] = 0;
    }
}
for (i=0; i<vyska; i=i+1) {
    tab[0][i][vaha] = 0;
    tab[0][i][cena] = 0;
    for (v=2; v<n+2; v=v+1) {
        tab[0][i][v] = 0;
    }
}

# dynamic. alg.
# jdeme z leveho dolniho rohu
# smerem k pravemu hornimu
for (v=1; v<vyska; v=v+1) {
    for (s=1; s<sirka; s=s+1) {
        
        # pokud krokem dolu (o vahu predmetu) vyjdu z prostoru,
        # ukladam automaticky dvojici zleva
        if ( (v-vahy[s-1]) < 0 ) {
            tab[s][v][vaha] = tab[s-1][v][vaha];
            tab[s][v][cena] = tab[s-1][v][cena];
            for (i=2; i<n+2; i=i+1) {
                tab[s][v][i] = tab[s-1][v][i];
            }

        # k nalezene dvojici pripocitam predmet, nad kterym
        # se nachazim a ukladam max z teto hodnoty a z hodnoty
        # policka o jeden krok vlevo
        } else {
            a = tab[s-1][v-vahy[s-1]][vaha] + vahy[s-1];
            b = tab[s-1][v-vahy[s-1]][cena] + ceny[s-1];
            if (tab[s-1][v][cena] >= b) {
                tab[s][v][vaha] = tab[s-1][v][vaha];
                tab[s][v][cena] = tab[s-1][v][cena];
                for (i=2; i<n+2; i=i+1) {
                    tab[s][v][i] = tab[s-1][v][i];
                }
            } else {
                tab[s][v][vaha] = a;
                tab[s][v][cena] = b;
                for (i=2; i<n+2; i=i+1) {
                    if (i-2 == s-1) {
                        tab[s][v][i] = 1;
                    } else {
                        tab[s][v][i] = tab[s-1][v-vahy[s-1]][i];
                    }
                }
            }
        }
    }
}

# vypis
open(1, fileOut);
WRITELN(fileOut, 'Cena nejlepsiho reseni: ' + tab[sirka-1][vyska-1][cena]);
konf = 'Konfigurace nejlepsiho reseni: ';
WRITELN(fileOut, konf);
for (i=2; i<n+2; i=i+1) {
    if (i == n+1) {
        WRITELN(fileOut, tab[sirka-1][vyska-1][i]);
    } else {
        WRITE(fileOut, tab[sirka-1][vyska-1][i]);
    }
}
close(fileOut);

END
